Modern central processing units (CPUs), such as, for example, Intel's Pentium® and Pentium® Pro microprocessors, include instruction pipelines in order to increase program execution speed. In the Intel Pentium® Pro microprocessor, for example, one pipeline includes an instruction fetch unit (IFU), an instruction decode unit (ID), and an instruction execution unit (EX). Each unit has its own functions, that is the IFU fetches program instructions, while the ID translates the instructions into micro-ops and the EX executes the micro-ops. Furthermore, in the pipeline arrangement, the IFU fetches instructions while the other units operate on previously fetched instructions.
During normal operation, the IFU fetches instructions from a main memory sequentially until a branch instruction is fetched. If the branch instruction is a conditional branch, branch prediction logic, in particular a branch table buffer (BTB), predicts whether or not the branch will be taken when the branch instruction is executed. The BTB includes a cache for storing previous branch predictions which contains 128 sets of 4 entries each. If the BTB predicts that the branch will not be taken, the IFU continues to fetch instructions sequentially. If the BTB instead predicts that a branch will be taken, the BTB instructs the IFU to instead fetch instructions starting from the branch target address. When the branch instruction is executed, a jump execution unit (JEU) (a component within the EX) instructs the BTB as to whether or not the branch was actually taken or not taken.
Unfortunately, however, in some microprocessors it is possible for the BTB to: (1) predict that a branch will occur at an address that does not contain a branch, or (2) predict a branch that will have a target address that is invalid. Such “bogus branch” predictions can occur for several reasons. First, the BTB stores an incomplete address, or “tag”, for its internal processing, which can cause the BTB to predict a branch at an incorrect address that shares the same tag as that of the correct address. For example, if the IFU should properly be directed to address 10A, the BTB may only store the tag xx0A. In such a case, the BTB may improperly direct the IFU to address 20A or 40A. Second, the BTB may predict a branch at an incorrect address when processing self-modifying code. In this case, it is possible that the code was changed for some outside reason and the predicted branch was eliminated.
“Bogus branch” predictions for reasons such as these, as well as others, slow down processing speeds and in worst case scenarios can lead to a catastrophic microprocessor failure (i.e., a flushing of the BTB and/or machine's pipeline; a crash). Prevention of and recovery from the execution of these bogus branches is therefore of paramount importance. Currently, the Pentium® Pro microprocessor detects some of these bogus branch problems by use of a branch address calculator (BAC). The BAC's functions include verifying that the BTB has not predicted that an unconditional branch will not be taken, and alternatively, insuring that there is actually a branch at the address the BTB predicts a branch would occur. In the case of a direct branch, that is a branch with a fixed target address, the BAC also verifies the existence of the branch's target. In the case of an indirect branch, however, where the target address is a function of another variable, the JEU verifies the presence of the branch target.
While some bogus branch detection can occur in a microprocessor such as the Pentium® Pro microprocessor, there remains, however, a need for a method and apparatus by which recovery from and prevention of bogus branches in an instruction pipeline effect only a minimal change in current pipeline procedures.